Search in Rotated Sorted Array Improved
Search in Rotated Sorted Arrayでの解答の計算量を半分に削減した改善版
こちらの方が直観的で理解しやすい気がする
numsに対してそのまま二分探索していて、midがどういった地点なのかによって次の探索範囲を決めている
code:solution.cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l <= r) {
int mid = l + (r-l)/2;
if (numsmid == target) return mid;
else if (numsl <= numsmid) {
if (numsl <= target && target < numsmid) r = mid-1;
else l = mid+1;
}
else {
if (numsmid < target && target <= numsr) l = mid+1;
else r = mid-1;
}
}
return -1;
}
};